#pragma once

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>

class Decomp
{
public:
    static std::vector<long long> decompose( long long n );
};

bool decompose_recursion( std::vector<long long> & storage, const long long n, long long k, size_t d = 0 ) {
    std::cout << std::setw( d * 3 ) << "" << "Trying decompose n = " << n << ", k = " << k << std::endl;

    // NOTE when must stop
    if( n == 0 ) {
        std::cout << "Nothing to decompose n = 0, k = " << k << std::endl;
        return true;
    } else if( k == 1 ) {
        if( n == k )
            storage.push_back( 1 );

        return n == 1;
    } else if( k == 0 ) {
        std::cout << std::setw( d * 3 ) << "" << "Stop decompose. k = 0 n = " << n << std::endl;
        return false;
    }

    while( !decompose_recursion( storage, n - k * k, std::min( std::max( k - 1, static_cast<long long>( 0 ) ), static_cast<long long>( sqrt( n - k * k ) ) ), d + 1 ) && k ) {
        std::cout << std::setw( d * 3 ) << "" << "Fail decompose for n = " << n << " k = " << k << std::endl;
        std::cout << std::setw( d * 3 ) << "" << "Set k: " << k << " => " << k - 1  << std::endl;
        --k;
        std::cout << std::setw( d * 3 ) << "" << "Trying decompose n = " << n << ", k = " << k << std::endl;
    }

    if( k ) {
        storage.push_back( k );
        return true;
    }

    return false;
}

std::vector<long long> Decomp::decompose( long long n )
{
    std::vector<long long> result;
    decompose_recursion( result, n * n, n - 1 );
    return result;
}
